Public-key cryptographic techniques are one type of key-based cipher. In public-key cryptography, each communicating party has a public/private key pair. The public key of each pair is made publicly available (or at least available to others who are intended to send encrypted communications), but the private key is kept secret. In order to communicate a message using encryption to a receiving party, an originating party encrypts the message using the public key of the receiving party and communicates the encrypted message to the receiving party. Upon receipt of the encrypted message, the receiving party decrypts it using its secret private key, and thereby recovers the original message.
The Diffie-Hellman protocol is a well-known example of public/private key cryptography. The DH protocol assumes that it is infeasible to compute gαβ (the shared secret) knowing only gα and gβ. For example, Alice and Bob agree to use a prime number p=23 and base g=5. Alice chooses a secret integer α=6, then sends Bob (gα mod p), which is 56 mod 23=8. Bob chooses a secret integer β=15, then sends Alice (gβ mod p), which is 515 mod 23=19. Alice computes (gβ mod p)α mod p, which is 196 mod 23=2. Bob computes (gα mod p)β mod p, which is 815 mod 23=2.
In recent years, the original DH protocol has been understood to be an example of a much more general cryptographic technique, the common element being the derivation of a shared secret value (i.e., a shared key) from one party's public key and another party's private key. The parties' key pairs may be generated anew at each run of the protocol.
New curve-based cryptography techniques have recently been employed for cryptography. Such techniques allow for more secure communications and for software manufacturers to appreciably reduce the incidence of unauthorized copying of software products. For example, product IDs have been generated using hyperelliptic curve cryptography techniques (HECC techniques). The resulting product IDs provide improved security. Moreover, such IDs can be configured such that the user is not required to input too many characters.
Jacobian groups of HECs are suitable for discrete logarithmic (DL) cryptosystems (e.g., ElGamal, DH and digital signature cryptosystems). In HECC, a Jacobian of a curve of genus g provides a number of points over a finite field F of q elements (Fq) where the number of points is approximately qg. In order to use the Jacobian of a curve for cryptography, suitable parameters must be chosen. One such parameter pertains to the underlying finite field Fq over which the curve is defined. Another important parameter is the cardinality N of the Fq-rational Jacobian of the curve. For many implementations of a discrete logarithm based cryptosystem, Fq should be a prime field, i.e., q is a prime number p (i.e., Fp), and N, the cardinality (or group order) of the Jacobian is prime or “close to” a prime number. Some refer to this as the group order problem on HECs over finite fields. Generally, solutions proceed by fixing a particular type of number field called a Complex Multiplication (CM) field (i.e., a totally imaginary field quadratic extension of a totally real number field) and then finding a suitable prime p and a possible group order N or possible group orders (e.g., N1, N2, . . . , Nn).
Generation of the parameter values for p and N can be time consuming for a genus 2 curve with a cryptographic size of 128 bits as it involves counting the number of points on the Jacobian of the curve over a prime field. As described herein, various exemplary algorithms are presented for generating cryptographically strong parameters (e.g., a “p” and one or more “N”s) for the CM construction of genus 2 curves.